package offer;

class offer35 {
}
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution35 {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        } else{
            Node newHead = new Node(head.val);
            Node pre =newHead;
            Node temp = null;
            Node tempFisrt =head.next;
            Node tempSecond = null;
//            newHead.next = tempSecond;
            while (tempFisrt!=null)
            {
                tempSecond = new Node(tempFisrt.val);
//                temp = tempFisrt.random;
                pre.next = tempSecond;
                pre = tempSecond;
                tempFisrt = tempFisrt.next;


            }
            Node first = head;
            Node tmp= head;
            Node second1 = newHead;
            Node second2 = newHead;

            while (first!=null)
            {
             temp= first.random;
             boolean flag = false;
             int count = 0;
             while (tmp!=null)
             {
                 if(temp ==tmp)
                 {
                     break;
                 }
                 count++;
                 tmp = tmp.next;
             }
             int i = 0;
             while (i<=count)
             {
                 second2 = second2.next;
             }
             second1.next = second2;
             second2 = head;
             tmp = head;
                first = first.next;
                second1 = second1.next;
            }
            return newHead;
        }


    }
}